/*
 * Graphs.h
 *
 *  Created on: 02/09/2012
 *      Author: marcio
 */

#ifndef GRAPHS_H_
#define GRAPHS_H_

#include "OrderedSet.h"
#include "OrderedBinaryRelation.h"
#include "ArrayOrderedSet.h"
#include "vEBTree.h"
#include "ArrayvEBTree.h"
#include "Graph.h"
#include "heap.h"
#include "ParallelizableOperation.h"

/*!
 * \class
 *
 * \brief Graphs
 *
 * This class encapsulates a set of algorithms to handle a graph structure.
 *
 * The most basic ones are the algorithms to coloring a graph and determine the connected
 * components of a graph.
 *
 * A coloring of a graph is a assignment of colors to the vertexes of the graph in such away
 * that if to vertexes are adjacent they have different colors.
 *
 * The connected components of a graph are a set of graphs such that each vertex and edge belong
 * to only one graph, the union of its vertexes sets and edge sets are the vertex set and the edge
 * set of the initial graph and all the graphs in the set are connected, what means that in each graph
 * there are a path between every pair of vertexes.
 */
template <class T, typename Z>
class Graphs {
public:

	/*!
	 * \brief Made a greedy coloring of the subgraph induced by the vertexes in R, with the order that they
	 * appear in R.
	 *
	 * Made a coloring, greedy coloring of the subgraph induced by the vertexes in R. The order used to
	 * built suc coloring is the same order that the vertexes appear in R. The algorithm visit each element
	 * in R, in order, and look for the smallest color not used in one of its neighbours to color it. If
	 * there is not such color a new color will be add to the set of possible colors.
	 *
	 * \param g the graph.
	 *
	 * \param cover the vector of colors to each vertex of R, the position i in this vector indicates the color
	 * of the vertex R[i] in the greedy coloring of the subgraph induced by R.
	 *
	 * \param factory a factory to OrderedSet to be used to instance the variables.
	 *
	 * \param R a vector representing the vertexes to be colored and the order to be used to color then.
	 *
	 * \param r the number of vertexes in the subgraph.
	 *
	 * \return the number of colors used to make a greedy coloring of the subgraph induced by R
	 */
	static long greedyCoverSort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r);

	/*!
	 * \brief Made a greedy coloring of the subgraph induced by the vertexes in R, using the Dsatur algorithm.
	 *
	 * Made a greedy coloring of the subgraph induced by the vertexes in R. The order used to do this coloring
	 * is determinate by an other algorithm, the Dsatur algorithm that keep track of the so called
	 * saturation degree of each vertex.
	 *
	 * The saturation degree of v is the number of already colored vertexes in the neighbourhood of iv.
	 * In each step the algorithm choose the vertex in R with the biggest saturation degree, in case of tie
	 * it choose the one with biggest degree. The vertexes are colored in this order.
	 *
	 * \param g the graph.
	 *
	 * \param cover the vector of colors to each vertex of R, the position i in this vector indicates the color
	 * of the vertex R[i] in the greedy coloring of the subgraph induced by R.
	 *
	 * \param factory a factory to OrderedSet to be used to instance the variables.
	 *
	 * \param R a vector representing the vertexes to be colored and the order to be used to color then.
	 *
	 * \param r the number of vertexes in the subgraph.
	 *
	 * \return the number of colors used to make a greedy coloring of the subgraph induced by R
	 */
	static long dsaturCoverSort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r);

	/*!
	 * \brief Cover the vertexes of the graph according its degree and the degree of its neighbours.
	 *
	 * Return an order to the vertexes in R, according the degrees in the subgraph induced for it.
	 * More clearly, if cover[i] = j it means that in the graph induced by the vertexes R[k] that has
	 * cover[k] < j, R[i] is a vertex with minimum degree.
	 *
	 * The integer value returned by this function is the biggest k such that k is the minimum degree
	 * in the subgraph induced by R[0] .... R[i] for all i < r.
	 *
	 * \param g the graph
	 *
	 * \param cover represent the order over the vertexes of g, the position i of this vector
	 * indicate the position of the vertex i in the order.
	 *
	 * \param R a vector representing the vertexes to be colored and the order to be used to color then.
	 *
	 * \param r the number of vertexes in the subgraph.
	 *
	 * \param factory a factory to OrderedSet to be used to instance the variables.
	 *
	 * \return the maximum mininum degree in the subgraph.
	 */
	static long mcrCoverSort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r);

	/*!
	 * \brief Made a greedy coloring of the subgraph induced by the vertexes in R, with the order that they
	 * appear in R.
	 *
	 * Made a coloring, greedy coloring of the subgraph induced by the vertexes in R. The order used to
	 * built suc coloring is the same order that the vertexes appear in R. The algorithm visit each element
	 * in R, in order, and look for the smallest color not used in one of its neighbours to color it. If
	 * there is not such color a new color will be add to the set of possible colors.
	 *
	 * The vertexes will be order in Ro according to the colors that each one receive, and cover[i]
	 * represents the color of the vertex Ro[i].
	 *
	 * \param g the graph.
	 *
	 * \param cover the vector of colors to each vertex of R, the position i in this vector indicates the color
	 * of the vertex Ro[i] in the greedy coloring of the subgraph induced by R.
	 *
	 * \param factory a factory to OrderedSet to be used to instance the variables.
	 *
	 * \param R a vector representing the vertexes to be colored and the order to be used to color then.
	 *
	 * \param r the number of vertexes in the subgraph.
	 *
	 * \param Ro the vertexes of R ordered according its colors.
	 *
	 * \return the number of colors used to make a greedy coloring of the subgraph induced by R
	 */
	static long greedySort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro);

	/*!
	 * \brief Made a greedy coloring of the subgraph induced by the vertexes in R, using the DSatur algorithm.
	 *
	 * Made a greedy coloring of the subgraph induced by the vertexes in R. The order used to do this coloring
	 * is determinate by an other algorithm, the Dsatur algorithm that keep track of the so called
	 * saturation degree of each vertex.
	 *
	 * The saturation degree of v is the number of already colored vertexes in the neighbourhood of iv.
	 * In each step the algorithm choose the vertex in R with the biggest saturation degree, in case of tie
	 * it choose the one with biggest degree. The vertexes are colored in this order.
	 *
	 * The vertexes will be order in Ro according to the colors that each one receive, and cover[i]
	 * represents the color of the vertex Ro[i].
	 *
	 * \param g the graph.
	 *
	 * \param cover the vector of colors to each vertex of R, the position i in this vetor indicates de color
	 * of the vertex Ro[i] in the greedy coloring of the subgraph induced by R.
	 *
	 * \param factory a factory to OrderedSet to be used to instance the variables.
	 *
	 * \param R a vector representing the vertexes to be colored and the order to be used to color then.
	 *
	 * \param r the number of vertexes in the subgraph.
	 *
	 * \param Ro the vertexes of R ordered according its colors.
	 *
	 * \return the number of colors used to make a greedy coloring of the subgraph induced by R
	 */
	static long dsaturSort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro);

	/*!
	 * \brief Order the vertexes of the graph according its degree and the degree of its neighbours.
	 *
	 * Return an order to the vertexes in R, according the degrees in the subgraph induced for it.
	 * More clearly, Ro[i] has the minimum degree in the subgraph induced by R[0]... R[i].
	 *
	 * The integer value returned by this function is the biggest k such that k is the minimum degree
	 * in the subgraph induced by R[0] .... R[i] for all i < r.
	 *
	 * The array cover represent a upper bound to the size of the clique that can be generate from
	 * a specified position of Ro. For instance if cover[i] = j, the subgraph R[0]... R[i] has
	 * as upper bound for its maximum clique j.
	 *
	 * \param g the graph
	 *
	 * \param cover represent the order over the vertexes of g, the position i of this vector
	 * indicate the position of the vertex i in the order.
	 *
	 * \param R a vector representing the vertexes to be colored and the order to be used to color then.
	 *
	 * \param r the number of vertexes in the subgraph.
	 *
	 * \param factory a factory to OrderedSet to be used to instance the variables.
	 *
	 * \param Ro the vertexes of R ordered according its degree and the deegre of its neighbours.
	 *
	 * \return the maximmum deegre of the vertexes in the graph.
	 */
	static long mcrSort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro);

	/*!
	 * \brief Determine the connected components of a graph.
	 *
	 * Determine the connected components of a graph. A connected component of a graph is a maximal
	 * subgraph such that for each pair u, v belong to the subgraph, there is a path between then in
	 * the subgraph.
	 *
	 * The connected components are view as a matrix of adjacency. comp is a matrix of bits, such that
	 * comp[i] is a bit array representing the vertexes belonging to that component.
	 *
	 * \param g the graph.
	 *
	 * \param comp the connected components of g as a matrix of adjacency.
	 *
	 * \param factory a abstract factory to sets used to instance the objects used.
	 *
	 * \return the number of connected components in the graph g.
	 */
	static long connectedComponents(Graph<T>* g, OrderedSet<long>** comp, OrderedSetFactory<long>* factory);

	/*!
	 * \brief Determine the connected components of a graph.
	 *
	 * Determine the connected components of a graph. A connected component of a graph is a maximal
	 * subgraph such that for each pair u, v belong to the subgraph, there is a path between then in
	 * the subgraph.
	 *
	 * The connected components are view as a array. comp is a vector of integer, such that
	 * comp[i] indicates the connected component each the vertex i belong.
	 *
	 * \param g the graph.
	 *
	 * \param comp the conected components of g as a caracteristic vector.
	 *
	 * \param factory a abstratc factory to sets used to instance the objects used.
	 *
	 * \return the number of connected components in the graph g.
	 */
	static long connectedComponents(Graph<T>* g, long* comp, OrderedSetFactory<long>* factory);

	/*!
	 * \brief Read a graph from a file.
	 *
	 * Read a graph from a file. The file must be in the DINAMC benchmark format.
	 *
	 * The file must start with a line "p x y" indicates the number of vertexes x
	 * and the number of edges(non edges) y. Each edge(non edge) must be in a line
	 * start for the caractere 'e' follow be the first endpoint of the edge plus
	 * space plus the second endpoint.
	 *
	 * The file must has no blank lines and each edge must be in a single line. If the
	 * file is not in the DINAMCS format an error will occur.
	 *
	 * \param g the graph to store the graph represented in the file
	 *
	 * \param graphFile the file in a specified form to represent a graph
	 *
	 * \param t indicates if we read the graph or its complement.
	 *
	 * \param factory a abstratc factory to sets used to instance the objects used.
	 *
	 * \return the number od edges in the graph.
	 */
	static long readDimacsGraph(Graph<T>** g, FILE * graphFile, graphType t, OrderedSetFactory<long>* factory, void* handle);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param d
	 *
	 * \param ng
	 *
	 * \param k
	 *
	 * \param rank
	 *
	 * \return
	 *
	 */
	static long greedySort(Graph<T>* g, long* d, long** ng, long k, long* rank);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param k
	 *
	 * \param rank
	 *
	 * \return
	 *
	 */
	static long greedyCoverSort(Graph<T>* g, long k, long* rank);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param d
	 *
	 * \param ng
	 *
	 * \param k
	 *
	 * \param rank
	 *
	 * \return
	 *
	 */
	static long dsaturSort(Graph<T>* g, long* d, long** ng, long k, long* rank);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param k
	 *
	 * \param rank
	 *
	 * \return
	 *
	 */
	static long dsaturCoverSort(Graph<T>* g, long k, long* rank);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param d
	 *
	 * \param ng
	 *
	 * \param rank
	 *
	 * \return
	 *
	 */
	static bool mcrSort(Graph<T>* g, long* d, long** ng, long* rank);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param maxd
	 *
	 * \param rank
	 *
	 * \return
	 *
	 */
	static bool mcrDegreeSort(Graph<T>* g, long* maxd, long* rank);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param k
	 *
	 * \param rank
	 *
	 * \return
	 *
	 */
	static double FCP2(Graph<T>* g, long k, long** rank);
};

long* graphs_sat;
long* graphs_deg;

int graphs_compar(const void* a, const void* b){
	int ret = graphs_sat[*(long*)a] - graphs_sat[*(long*)b];
	if(ret != 0) return ret;
	else return graphs_deg[*(long*)a] - graphs_deg[*(long*)b];
}


template<class T, typename Z>
long Graphs<T, Z>::greedyCoverSort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r){
	long i, v, co, n = g->nverts();
	OrderedSet<long>* colors[n];
	OrderedSet<long>::Iterator* it;

	//induced subgraph
	OrderedSet<long>* bitR = factory->newOrderedSet(n);
	for(long j = 0 ; j < r; j++)bitR->toSet(R[j]);

	//initialize the colors, each vetor represents the set of colors avaible for
	//each vertex.
	for(long j = 0 ; j < n; j++)
		colors[j] = factory->newOrderedSet(r);

	//greedy coloring
	while(i < r ){
		//in order visit each vertex of R
		v = R[i++];
		co = colors[v]->firstInCompl();
		//determine its color
		for(long j = 0; j < r; j++)if(R[j] == v) (*cover)[j] = co;

		//remove the color to the possible colors of its neigbours
		it = g->neig(v)->newSetIterator(bitR);
		it->start();
		while(it->hasNext()){
			colors[it->next()]->toSet(co);
		}
	}

	//clean memory
	for(long j = 0 ; j < r; j++)
		delete colors[j];

	return 0;
}

template<class T, typename Z>
long Graphs<T, Z>::dsaturCoverSort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r){
	long i = r, v, u, co, n = g->nverts();
	long* satdegree = new long[n];
	long* degree = new long[n];

	graphs_sat = satdegree;
	graphs_deg = degree;
	memset(satdegree, 0, n*sizeof(long));

	//biult an heap we the elements in R.
	long* RR = new long[r];
	memcpy(R,RR,r*sizeof(long));
	heapify(RR, r, sizeof(long), graphs_compar);

	OrderedSet<long>* colors[n];
	OrderedSet<long>::Iterator* it;

	//create a bit vetor to the elements in R to be used as a filter
	OrderedSet<long>* bitR = factory->newOrderedSet(n);
	OrderedSet<long>* degR = factory->newOrderedSet(n);
	for(long j = 0 ; j < r; j++)bitR->toSet(R[j]);

	//initialize the vector of degree
	for(long j = 0; j < r; j++){
		degR->allToSet();
		 ParalelizableOperation<Z>::setIntersec(degR, bitR);
		 ParalelizableOperation<Z>::setIntersec(degR, g->neig(R[j]));
		degree[R[j]] = degR->cardOfSet();
	}

	//initialize the vetor of colors
	for(long j = 0 ; j < n; j++)
		colors[j] = factory->newOrderedSet(r);

	//coloring
	while(i >= 0){
		//color the first in the heap
		v = RR[0];
		heappoll(RR, i--, sizeof(long), graphs_compar);
		co = colors[v]->firstInCompl();

		//find its position in the cover vector
		for(long j = 0; j < r; j++)if(R[j] == v) (*cover)[j] = co;

		//update the saturation degree of its neighbours
		it = g->neig(v)->newSetIterator(bitR);
		it->start();
		while(it->hasNext()){
			u = it->next();
			colors[u]->toSet(co);
			satdegree[u]++;
		}

		//upadete the heap
		heapify(RR, i, sizeof(long), graphs_compar);
	}

	for(long j = 0 ; j < n; j++)delete colors[j];

	delete satdegree;
	delete degree;

	return 0;
}

template<class T, typename Z>
long Graphs<T, Z>::mcrCoverSort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r){
	long n = g->nverts();
	long degin[n];
	long degree[n];
	long i = r;
	long v;

	//maximum minimum degree
	long maxmindeg = 0;

	//to use the same function of comparation
	graphs_deg = degree;
	graphs_sat = degin;

	memset(degin, 0, n*sizeof(long));
	memset(degree, 0, n*sizeof(long));

	//sets to represent R.
	OrderedSet<long>* bitR = factory->newOrderedSet(n);
	OrderedSet<long>* degR = factory->newOrderedSet(n);
	for(long j = 0 ; j < r; j++)bitR->toSet(R[j]);

	for(long j = 0; j < r; j++){
		degR->allToSet();
		 ParalelizableOperation<Z>::setIntersec(degR, bitR);
		 ParalelizableOperation<Z>::setIntersec(degR, g->neig(R[j]));
		degree[R[j]] = degR->cardOfSet();
	}

	long* RR = new long[r];
	memcpy(R,RR,r*sizeof(long));
	heapify(RR, r, sizeof(long), graphs_compar);
	OrderedSet<long>::Iterator* it;

	//ordering
	while(i > 0){
		//determine the head of the heap
		v = RR[0];
		maxmindeg = maxmindeg < degin[v]? degin[v] : maxmindeg;
		heappoll(RR, i--, sizeof(long),graphs_compar);

		//update info
		for(long j = 0; j < r; j++)if(R[j] == v) (*cover)[j] = i;
		it = g->neig(v)->newSetIterator(bitR);
		it->start();
		while(it->hasNext()){
			degin[it->next()]++;
		}
		heapify(RR, i, sizeof(long), graphs_compar);
	}
	return maxmindeg;
}

template<class T, typename Z>
long Graphs<T, Z>::greedySort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro){
	long i, v, co, n = g->nverts();
	OrderedSet<long>* colors[n];
	OrderedSet<long>* vert[n];
	OrderedSet<long>::Iterator* it;

	//induced subgraph
	OrderedSet<long>* bitR = factory->newOrderedSet(n);
	for(long j = 0 ; j < r; j++)bitR->toSet(R[j]);

	//initialize the colors, each vetor represents the set of colors avaible for
	//each vertex.
	for(long j = 0 ; j < n; j++){
		colors[j] = factory->newOrderedSet(r);
		vert[j] = factory->newOrderedSet(r);
	}

	//coloring
	while(i < r ){
		//visit a vertex
		v = R[i++];

		//give a color
		co = colors[v]->firstInCompl();
		vert[co]->toSet(v);

		//update the vetors of its neigbours
		it = g->neig(v)->newSetIterator(bitR);
		it->start();
		while(it->hasNext()){
			colors[it->next()]->toSet(co);
		}
	}

	//fill in the vectos cover and Ro
	long index = 0;
	for(long j = 0 ; j < r; j++){
		it = vert[j]->newSetIterator();
		while(it->hasNext()){
			(*Ro)[index] = it->next();
			(*cover)[index++] = j;
		}
	}

	//clean memory
	for(long j = 0 ; j < n; j++){
		delete vert[j];
		delete colors[j];
	}

	return 0;
}

template<class T, typename Z>
long Graphs<T, Z>::dsaturSort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro){
	long i = r, v, u, co, n = g->nverts();
	long* satdegree = new long[n];
	long* degree = new long[n];

	graphs_sat = satdegree;
	graphs_deg = degree;
	memset(satdegree, 0, n*sizeof(long));

	long* RR = new long[r];
	memcpy(R,RR,r*sizeof(long));
	heapify(RR, r, sizeof(long), graphs_compar);

	OrderedSet<long>* colors[n];
	OrderedSet<long>* vert[n];
	OrderedSet<long>::Iterator* it;

	//bit set to represent R
	OrderedSet<long>* bitR = factory->newOrderedSet(n);
	for(long j = 0 ; j < r; j++)bitR->toSet(R[j]);

	//color avaible to each vertex
	for(long j = 0 ; j < n; j++){
		colors[j] = factory->newOrderedSet(r);
		vert[j] = factory->newOrderedSet(r);
	}

	OrderedSet<long>* degR = factory->newOrderedSet(n);

	//calcute the degree in the subgraph
	for(long j = 0; j < r; j++){
		degR->allToSet();
		 ParalelizableOperation<Z>::setIntersec(degR, bitR);
		 ParalelizableOperation<Z>::setIntersec(degR, g->neig(R[j]));
		degree[R[j]] = degR->cardOfSet();
	}

	//coloring
	while(i >= 0){
		//visit the vertex
		v = RR[0];
		heappoll(RR, i--, sizeof(long),graphs_compar);

		//determine its color
		co = colors[v]->firstInCompl();
		vert[co]->toSet(v);

		//update the colors avaible in the neighbours
		it = g->neig(v)->newSetIterator(bitR);
		it->start();
		while(it->hasNext()){
			u = it->next();
			colors[u]->toSet(co);
			satdegree[u]++;
		}
		heapify(RR, i, sizeof(long), graphs_compar);
	}

	//ordering
	long index = 0;
	for(long j = 0 ; j < r; j++){
		it = vert[j]->newSetIterator();
		while(it->hasNext()){
			(*Ro)[index] = it->next();
			(*cover)[index++] = j;
		}
	}

	for(long j = 0 ; j < n; j++){
		delete vert[j];
		delete colors[j];
	}
	delete satdegree;
	delete degree;

	return 0;
}

template<class T, typename Z>
long Graphs<T, Z>::mcrSort(Graph<T>* g, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro){
	long n = g->nverts();
	long degin[n];
	long degree[n];
	long i = r;
	long v;
	long maxmindeg = 0;
	long maxdeg = 0;

	graphs_deg = degree;
	graphs_sat = degin;

	memset(degin, 0, n*sizeof(long));
	memset(degree, 0, n*sizeof(long));

	OrderedSet<long>* bitR = factory->newOrderedSet(n);
	OrderedSet<long>* degR = factory->newOrderedSet(n);
	for(long j = 0 ; j < r; j++)bitR->toSet(R[j]);

	//calculate the degree in the subgraph
	for(long j = 0; j < r; j++){
		degR->allToSet();
		 ParalelizableOperation<Z>::setIntersec(degR, bitR);
		 ParalelizableOperation<Z>::setIntersec(degR, g->neig(R[j]));
		degree[R[j]] = degR->cardOfSet();
		maxdeg = maxdeg < degree[R[j]]? degree[R[j]] : maxdeg;
	}

	long* RR = new long[r];
	memcpy(R,RR,r*sizeof(long));
	heapify(RR, r, sizeof(long), graphs_compar);
	OrderedSet<long>::Iterator* it;

	//ordering
	while(i > 0){
		(*Ro)[i] = v = RR[0];
		maxmindeg = maxmindeg < degin[v]? degin[v] : maxmindeg;
		heappoll(RR, i--, sizeof(long),graphs_compar);
		(*cover)[i] = i < maxdeg ? i : maxdeg;
		it = g->neig(v)->newSetIterator(bitR);
		it->start();
		while(it->hasNext()){
			degin[it->next()]++;
		}
		heapify(RR, i, sizeof(long), graphs_compar);
	}
	return maxmindeg;
}

template<class T, typename Z>
long Graphs<T, Z>::connectedComponents(Graph<T>* g, OrderedSet<long>** comp, OrderedSetFactory<long>* factory){
	//TODO
	return 0;
}

template<class T, typename Z>
long Graphs<T, Z>::connectedComponents(Graph<T>* g, long* comp, OrderedSetFactory<long>* factory){
	//TODO
	return 0;
}

template<class T, typename Z>
long Graphs<T, Z>::readDimacsGraph(Graph<T>** g, FILE* graphFile, graphType t, OrderedSetFactory<long>* factory, void* handle){
	char type = ' ';
	char linestr[100];
	char* datastr;
	long i, j;
	long n;
	long long int m;

	n = 0;
	m = 0;

	printf("\t#Starting read...\n");

	while (type != 'p') {
		type = fgetc(graphFile);
		if (type != EOF) {

			/* header */
			if (type == 'c') {
				datastr = fgets(linestr, 100, graphFile);
				if (datastr != NULL)
					printf("%s", linestr);
				else
					return 0;
			}

			/* Vertices */
			if (type == 'p') {
				datastr = fgets(linestr, 100, graphFile);
				if (datastr == NULL)
					return 0;
				datastr = strtok(linestr," ");
				printf("\tdatastr:%s\n",datastr);
				n = atoi(datastr);

				datastr = strtok(NULL," ");
				printf("\tdatastr:%s\n",datastr);
				m = atoll(datastr);

					printf("Graph with (%lu) vertices and (%llu) edges.\n", n, m);
				if (t == GT_COMPLEMENT)
					m = ((((long long) (n))*((long long) (n)) - ((long long) n)) >> ((long long) 1)) - m;
			}
		}
	}

	////
	// Graph variables
	////
	*g = new Graph<T>(n, factory, handle);
	if (t != GT_GRAPH) {
		(*g)->addAllEdges();
		for (i = 0; i < n; i++)
			(*g)->delEdge(i, i);
		m = (*g)->nedges();
	}
	else m = 0;

	type = fgetc(graphFile);
	while (type != EOF) {
		/* Edges */
		if (type == 'e') {
			datastr = fgets(linestr, 100, graphFile);
			if (datastr == NULL)
				return 0;

			datastr = strtok(linestr," ");
			i = atoi(datastr) - 1;

			datastr = strtok(NULL," ");
			j = atoi(datastr) - 1;

			if (t == GT_GRAPH) {
				(*g)->addEdge(i, j);
				(m)++;
			}
			else {
				(*g)->delEdge(i, j);
				(m)--;
			}
		}
		else {
			datastr = fgets(linestr, 100, graphFile);
			if (datastr != NULL)
				printf(" %s\n", linestr);
			else
				return 0;
		}
		type = fgetc(graphFile);
	}
	printf("\t#Finished read\n");
	return n;
}
//>>>>>>>>>>>>>>>>>Old functions inherit from the old implementation>>>>>>>>>>>>>>>>>>>>>>>>>>.

#define graphs_declareListForAssignment(r,k) 	long _i_; \
							long _next_[r+1]; \
							for (_i_ = 0; _i_ <= r; _i_++) _next_[_i_] = r; \
							long _covhead_[k+1]; \
							for (_i_ = 0; _i_ <= k; _i_++) _covhead_[_i_] = r

#define callAssignClique(g, k, cover, i, coversize)	assignCliqueByMatrix(g, k, cover, i, &coversize, _next_, _covhead_)


static inline long graphs_assignCliqueByBitParallel(long **colors, long **adj, long k, long wordsize, long adj_bitl, long i, long mincolor, long *coversize) {
      long c=0,j=0,found=0;
      unsigned long aux=0;

      for (c = mincolor; c < (*coversize); c++) {
              for(j = 0; j < adj_bitl; j++) {
                   aux= colors[c][j] & adj[i][j];    // We are not using mask to zero vertex out of scope
                   if(aux!=0) {
                      found = 0;
                      break;
                   }
                   else found = 1;
              }
	      if(found) break;
      }
      if(c <= k) {
           colors[c][i/wordsize] |= (1 << (wordsize - (i%wordsize) -1));
           if( (c+1) > (*coversize) ) (*coversize)++;
      }

      return c + 1;
}

// sort specified vertices of a specified graph in a non-increasing order of degrees, in the
// following sense:
// in a subgraph of the specified graph induced by a set of vertices V = {V_1,V_2, ... ,V_i}, for 1 ≤ i ≤ r,
// it holds that V_i always has the maximum rank and the minimum degree in V.
// exdeg is used to break ties
// 2 vectors of r longegers are defined in the C function stack
// vertices R[j] having rank[j]=min { rank[i] | i=0,1,...,r-1 } induce a regular subgraph
// mcr order is obtained by sorting R in a non-increasing order of rank
template<class T, typename Z>
bool Graphs<T, Z>::mcrSort(Graph<T>* g, long* d, long** ng, long* rank) {
	// degrees used locally
	long r = g->nverts();
	long locald[r];
	memcpy(locald, d, r*sizeof(long));
	// used to break ties
	long exdeg[r];
	// a negative number indicates that this parameter is not known
	memset(exdeg, -1, r*sizeof(long));

	// determine min deg
	long Rmin[r];
	long nrmin = 1;
	long i = r - 1;

	long imin = 0;
	Rmin[0] = imin;
	long degrmin = locald[imin];
	long j;
	for (j = imin + 1; j < r; j++)
		if (locald[j] < degrmin) {
			nrmin = 1;
			Rmin[0] = j;
			degrmin = locald[j];
		}
		else if (locald[j] == degrmin)
			Rmin[nrmin++] = j;

	long rmin;
	memset(rank, 0, r*sizeof(long));
	while (i >= nrmin) {
		rmin = 0;
		if (nrmin > 1) {
			for (j = 1; j < nrmin; j++) {
				if (exdeg[Rmin[rmin]] < 0) {
					exdeg[Rmin[rmin]]=0;
					long l;
					for (l = 0; l < locald[Rmin[rmin]]; l++)
						if (!rank[ng[Rmin[rmin]][l]])
							exdeg[Rmin[rmin]] += locald[ng[Rmin[rmin]][l]];
				}
				if (exdeg[Rmin[j]] < 0) {
					exdeg[Rmin[j]]=0;
					long l;
					for (l = 0; l < locald[Rmin[j]]; l++)
						if (!rank[ng[Rmin[j]][l]])
							exdeg[Rmin[j]] += locald[ng[Rmin[j]][l]];
				}
				if (exdeg[Rmin[j]] < exdeg[Rmin[rmin]])
					rmin = j;
			}
		}

		rank[Rmin[rmin]] = --i;

		while (rank[imin])
			imin++;
		for (j = 0; j < locald[Rmin[rmin]]; j++)
			if (!rank[ng[Rmin[rmin]][j]]) {
				exdeg[ng[Rmin[rmin]][j]] -= locald[Rmin[rmin]];
				locald[ng[Rmin[rmin]][j]]--;
			}

		Rmin[0] = imin;
		nrmin = 1;
		degrmin = locald[imin];
		for (j = imin + 1; j < r; j++)
			if (!rank[j])
				if (locald[j] < degrmin) {
					nrmin = 1;
					Rmin[0] = j;
					degrmin = locald[j];
				}
				else if (locald[j] == degrmin)
					Rmin[nrmin++] = j;
	}

	long maxno = 0;
	--i;
	for (j = imin; j < r; j++)
		if (!rank[j]) {
			rank[j] = i;
			maxno++;
		}

	return locald[imin] == maxno - 1;
}

// sort specified vertices of a specified graph in a non-increasing order of degrees, in the
// following sense:
// in a subgraph of the specified graph induced by a set of vertices V = {V_1,V_2, ... ,V_i}, for 1 ≤ i ≤ r,
// it holds that V_i always has the maximum rank and the minimum degree in V.
// exdeg is used to break ties; maximum rank is returned
// 3 vectors of r longegers are defined in the C function stack
// if true is returned, then vertices R[j] having rank[j]=max rank induce a clique
template<class T, typename Z>
bool Graphs<T, Z>::mcrDegreeSort(Graph<T>* g, long * maxd, long * rank) {
	// degrees used locally
	long i, j, r = g->nverts();
	long deg[r];
	memset(deg, 0, r*sizeof(long));
	// used to break ties
	long exdeg[r];
	*maxd = 0;
	for (i = 0; i < r; i++) {
		for (j = i + 1; j < r; j++)
			if (g->hasEdge(i, j)) {
				if (++deg[i] > *maxd)
					*maxd = deg[i];
				if (++deg[j] > *maxd)
					*maxd = deg[j];
			}
		exdeg[i] = -1;
	}

	// determine min deg
	long Rmin[r];
	long nrmin = 1;
	long imin = 0;
	Rmin[0] = imin;
	long degrmin = deg[imin];
	for (j = imin + 1; j < r; j++)
		if (deg[j] < degrmin) {
			nrmin = 1;
			Rmin[0] = j;
			degrmin = deg[j];
		}
		else if (deg[j] == degrmin)
			Rmin[nrmin++] = j;

	long rmin;
	memset(rank, 0, r*sizeof(long));
	i = r;
	while (i > nrmin) {
		rmin = 0;
		if (nrmin > 1) {
			if (exdeg[Rmin[rmin]] < 0) {
				exdeg[Rmin[rmin]]=0;
				long l;
				for (l = imin; l < r; l++)
					if (rank[l] == 0 && l != Rmin[rmin] && g->hasEdge(Rmin[rmin], l))
						exdeg[Rmin[rmin]] += deg[l];
			}
			for (j = 1; j < nrmin; j++) {
				if (exdeg[Rmin[j]] < 0) {
					exdeg[Rmin[j]]=0;
					long l;
					for (l = imin; l < r; l++)
						if (rank[l] == 0 && l != Rmin[j] && g->hasEdge(Rmin[j], l))
							exdeg[Rmin[j]] += deg[l];
				}
				if (exdeg[Rmin[j]] < exdeg[Rmin[rmin]])
					rmin = j;
			}
		}

		rank[Rmin[rmin]] = i--;

		while (rank[imin] != 0)
			imin++;
		for (j = imin; j < r; j++)
			if (rank[j] == 0 && g->hasEdge(Rmin[rmin], j)) {
				exdeg[j] -= deg[Rmin[rmin]];
				deg[j]--;
			}

		Rmin[0] = imin;
		nrmin = 1;
		degrmin = deg[imin];
		for (j = imin + 1; j < r; j++)
			if (rank[j] == 0)
				if (deg[j] < degrmin) {
					nrmin = 1;
					Rmin[0] = j;
					degrmin = deg[j];
				}
				else if (deg[j] == degrmin)
					Rmin[nrmin++] = j;
	}

	long maxno = 0;
//	--i;
	for (j = imin; j < r; j++)
		if (rank[j] == 0) {
			rank[j] = i;
			maxno++;
		}

	return deg[imin] == maxno - 1;
}

static inline long graphs_assignByList(long* d, long** ng, long k, long* cover, long i, long* coversize, long* clique) {
	long j;
	// current clique starts with size 1
	cover[i] = 0;

	// find clique to include vertex as the smallest
	// not appearing in the neighborhood of i
	memset(clique, 0, ((*coversize)+1)*sizeof(long));
	for (j = 0; j < d[i]; j++)
		clique[cover[ng[i][j]]] = 1;

	long c = 1;
	while (c <= *coversize && clique[c])
		c++;
	if (c <= k) {
		if (c > *coversize)
			(*coversize)++;
		cover[i] = c;
	}

	return c;
}

template<class T, typename Z>
long Graphs<T, Z>::greedySort(Graph<T>* g, long* d, long**  ng, long k, long* rank) {
	long coversize = 0;
	long i, r = g->nverts();
	 // array, indexed by the cliques, used to mark all cliques in the neighborhood of a vertex
	long clique[k+1];

	memset(rank, 0, r*sizeof(long));
	for (i = 0; i < r; i++) {
		graphs_assignByList(d, ng, k, rank, i, &coversize, clique);
	}

	return coversize;
}

template<class T, typename Z>
static inline long graphs_assignCliqueByMatrix(Graph<T>* g, long k, long* cover, long i, long* coversize, long* next, long* covhead) {
	long c = 0, r = g->nverts();
	long cc = covhead[c];
	long antcc = r;
	while (!cover[i] && c < *coversize){
		// search for cover to add
		for (; cc != covhead[c+1] && g->hasEdge(i, cc); antcc = cc, cc = next[cc]);
		if (cc == covhead[c+1])
			cover[i] = c + 1;
		else {
			c++;
			for (; cc != covhead[c]; antcc = cc, cc = next[cc]);
		}
	}
	if (c == *coversize && *coversize < k) {
		(*coversize)++;
		covhead[c] = i;
		cover[i] = c + 1;
	}
	// include i in the tail of cover list
	next[antcc] = i;
	next[i] = cc;

	return c + 1;
}

// sort R according to a clique cover of the subgraph induced by R
// clique cover is determined using greedy algorithm in the vertex order specified by the input value of R
// 1 vector of r longegers are defined in the C function stack
// it returns the size of the clique cover and sets the cover array such that:
// for i in 0, ..., r-1, the entry cover[i] contains the size of a clique
// cover of the subgraph induced by R[0], ..., R[i]
template<class T, typename Z>
long Graphs<T, Z>::greedyCoverSort(Graph<T>* g, long k, long* rank) {
	long coversize = 0, r = g->nverts();
	graphs_declareListForAssignment(r, k);

	long i;
	for (i = 0; i < r; i++) {
		rank[i] = 0;
		callAssignClique(g, k, rank, i, coversize);
	}

	return coversize;
}

// sort R according to a clique cover or coloring of the subgraph induced by R,
// depending whether d and ng represents neighborhoods or antineighborhoods.
// index in R is used as last break tie condition
// Assuming they represent antineighborhoods, clique cover is determined using dsatur
// 4 vectors of r longegers are defined in the C function stack
// it returns the size of the clique cover and sets the cover array such that:
// for i in 0, ..., r-1, the entry cover[i] contains the size of a clique
// cover of the subgraph induced by all vertices of rank less than or equal to cover[i]
// the number of cliques in the cover is returned. Cliques returned in the cover array are numbered from 1 to number of cliques in the
template<class T, typename Z>
long Graphs<T, Z>::dsaturSort(Graph<T>* g, long* d, long** ng, long k, long* rank) {
	long r = g->nverts();
	long next[r+1];
	long prev[r+1];
	long satdeglist[r];
	long satdeg[r];
	// array, indexed by the cliques, used to mark all cliques in the neighborhood of imaxantideg
	long clique[k+1];
	long nclique = 0;

	long i, j;

	// initially, all cliques are empty, all saturation degrees are 0 and
	// its doubly linked list contains all vertices
	memset(rank, 0, r*sizeof(long));
	memset(satdeg, 0, r*sizeof(long));
	for (i = 0; i < r; i++) {
		next[i] = i+1;
		prev[i] = i-1;
		satdeglist[i] = r;
	}
	satdeglist[0] = 0;
	prev[0] = r;

	long ncovered;
	long maxsatdeg = 0;
	long imaxantideg;
	for (ncovered = 0; ncovered < r; ncovered++) {
		// find vertex with max antideg among those with max satdeg
		i = satdeglist[maxsatdeg];
		imaxantideg = i;
		while (next[i] < r) {
			i = next[i];
			if (d[i] > d[imaxantideg])
				imaxantideg = i;
		}

		// remove vertex form its doubly linked list
		if (prev[imaxantideg] == r) {
			satdeglist[maxsatdeg] = next[imaxantideg];
			if (ncovered < r - 1)
				while (satdeglist[maxsatdeg] == r)
					maxsatdeg--;
		}
		else
			next[prev[imaxantideg]] = next[imaxantideg];
		prev[next[imaxantideg]] = prev[imaxantideg];

		// find clique to include vertex as the smallest
		// not appearing in the neighborhood of imaxantideg
		long c = graphs_assignByList(d, ng, k, rank, imaxantideg, &nclique, clique);

		// update satdeglist
		if (c <= k)
			for (i = 0; i < d[imaxantideg]; i++) {
				long ii = ng[imaxantideg][i];
				if (!rank[ii]) {
					for (j = 0; j < d[ii] && (ng[ii][j] == imaxantideg || rank[ng[ii][j]] != c); j++);
					if (j == d[ii]) {
						// remove i from list
						if (prev[ii] == r)
							satdeglist[satdeg[ii]] = next[ii];
						else
							next[prev[ii]] = next[ii];
						prev[next[ii]] = prev[ii];

						// insert i in next list
						satdeg[ii]++;
						next[ii] = satdeglist[satdeg[ii]];
						prev[ii] = r;
						prev[satdeglist[satdeg[ii]]] = ii;
						satdeglist[satdeg[ii]] = ii;

						if (satdeg[ii] > maxsatdeg)
							maxsatdeg = satdeg[ii];
					}
				}
			}
	}

	return nclique;
}

// sort R according to a clique cover of the subgraph induced by R,
// using the symmetric adjacency matrix
// clique cover is determined using dsatur
// 5 vectors of r longegers are defined in the C function stack
// it returns the size of the clique cover and sets the cover array such that:
// for i in 0, ..., r-1, the entry cover[i] contains the size of a clique
// cover of the subgraph induced by all vertices of rank less than or equal to cover[i]
// the number of cliques in the cover is returned. Cliques returned in the cover array are numbered from 1 to number of cliques in the
template<class T, typename Z>
long Graphs<T, Z>::dsaturCoverSort(Graph<T>* g, long k, long* rank) {
	long r = g->nverts();
	graphs_declareListForAssignment(r, k);

	long antideg[r];
	long next[r+1];
	long prev[r+1];
	long satdeglist[r];
	long satdeg[r];
	long nclique = 0;

	long i, j;

	// initially, all cliques are empty, all saturation degrees are 0 and
	// its doubly linked list contains all vertices
	memset(rank, 0, r*sizeof(long));
	memset(satdeg, 0, r*sizeof(long));
	memset(antideg, 0, r*sizeof(long));
	for (i = 0; i < r; i++) {
		next[i] = i+1;
		prev[i] = i-1;
		satdeglist[i] = r;
		for (j = i + 1; j < r; j++)
			if (!g->hasEdge(i, j)) {
				antideg[i]++;
				antideg[j]++;
			}
	}
	satdeglist[0] = 0;
	prev[0] = r;

	long ncovered;
	long maxsatdeg = 0;
	long imaxantideg;
	for (ncovered = 0; ncovered < r; ncovered++) {
		// find vertex with max antideg among those with max satdeg
		i = satdeglist[maxsatdeg];
		imaxantideg = i;
		while (next[i] < r) {
			i = next[i];
			if (antideg[i] > antideg[imaxantideg])
				imaxantideg = i;
		}

		// remove vertex form its doubly linked list
		if (prev[imaxantideg] == r) {
			satdeglist[maxsatdeg] = next[imaxantideg];
			if (ncovered < r - 1)
				while (satdeglist[maxsatdeg] == r)
					maxsatdeg--;
		}
		else
			next[prev[imaxantideg]] = next[imaxantideg];
		prev[next[imaxantideg]] = prev[imaxantideg];

		long c = callAssignClique(g, k, rank, imaxantideg, nclique);

		// update satdeglist
		if (c <= k)
			for (i = 0; i < r; i++)
				if (!g->hasEdge(imaxantideg, i) && !rank[i]) {
					for (j = 0; j < r && (g->hasEdge(i, j) || j == imaxantideg || rank[j] != c); j++);
					if (j == r) {
						// remove i from list
						if (prev[i] == r)
							satdeglist[satdeg[i]] = next[i];
						else
							next[prev[i]] = next[i];
						prev[next[i]] = prev[i];

						// insert i in next list
						satdeg[i]++;
						next[i] = satdeglist[satdeg[i]];
						prev[i] = r;
						prev[satdeglist[satdeg[i]]] = i;
						satdeglist[satdeg[i]] = i;

						if (satdeg[i] > maxsatdeg)
							maxsatdeg = satdeg[i];
					}
				}
	}

	return nclique;
}


#endif /* GRAPHS_H_ */
